COMMENT ⊗   VALID 00003 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.require "memo.pub[let,jmc]" source
C00029 00003	.skip to column 1
C00031 ENDMK
C⊗;
.require "memo.pub[let,jmc]" source;
.cb ARTIFICIAL INTELLIGENCE
.skip 1
.ONCE CENTER
by John McCarthy

.skip 1
.once center
[draft of article on artificial intelligence for Collier's Encyclopedia]


	Artificial intelligence is the branch of computer science concerned
with making machines behave intelligently.  Its scientific part involves
discovering what intellectual mechanisms are needed to solve various
problems, and its engineering part involves writing computer programs or
building machines to solve one or another kind of problem.
It ultimate goal is to understand
intelligence well enough to make computers more intelligent than people,
but we are far from it today,
and some people don't believe it possible.

	The idea of intelligent machines is old in legend and fiction,
but legend and fiction are more concerned with how an artificial
intelligent being might behave than with how it might be made.
Until the 1950s, robots were usually depicted as enemies of mankind
usually arising from human weakness or greed.  They then played a
brief role as an oppressed minority, and in the 1960s they became
neurotic and even guilt ridden just like the human characters in
literature.

	In the early 1900s, the Spanish inventor Torres y Quevedo
made a machine that could checkmate its opponent with a rook and
king against a king, and speculated intelligently about the possibilities
of intelligent machines.  However, the first serious work on
AI began with the invention of
digital computers after World War II.  Perhaps the
first serious scientific article on the subject was written by
the British mathematician Alan Turing in 1950 and was entitled
%2Computing Machinery and Intelligence%1.
It was in 1954 that the first full time research group was founded
at Carnegie-Mellon University in Pittsburgh by Allen Newell and
Herbert Simon.

	Like any other complex problem, artificial intelligence is
studied by finding subproblems that can be worked on separately
and then combining the solutions.  Here are some of the research
areas that have been studied.

.item←0
%3Search%1

	When the computer has to decide on an action, it may have
a number of choices.  Each possible action may a number of different
consequences depending on unknown facts about the world, and each
consequence may give new possible actions, and so on.  Sometimes
the possibilities come to an end in a state of affairs that can
be conclusively evaluated, but usually the programmer has to make
the analysis stop
short of a conclusive answer, and devise some approximate way of
evaluating the resulting situation.

	The first experimental studies of searching such %2trees of
possibilities%1 were made using games like chess, and the performance of
chess programs is one good measure of progress in the search part of
artificial intelligence.  The 1950s programs performed much worse than
expected, and one reason because is unexpectedly difficulty for a chess
master who is also a programmer to make a program that analyzes positions
the way he analyzes them himself.  When we try we miss many aspects of our
own ways of thinking that seem obvious when someone finally points them
out.

	Thus one chess master's program looked at the seven most
plausible moves and the seven plausible replies to each of these
and seven replies to each of these and seven to each of these for
a total of 7%8x%17%8x%17%8x%17 = 2401 final positions.  He didn't notice that
most of these positions were examined unnecessarily, because
when a move has been shown to be worse than a previously examined
move of the same player by finding one reply that refutes it,
it is not necessary to examine other replies.  This observation
(illustrated in the figure)
has been elaborated into a method called the alpha-beta heuristic
for reducing search used by all modern game playing programs.  The joke is
that it
is also used by all human players, modern or not, and whether
they realize it or not.  Most likely, our
programs today lack features of human play that will seem equally
obvious once pointed out.

	In 1967 an M.I.T. chess program won the class D trophy in
a tournament. In 1977 a Northwestern University program by
Atkins and Slate won the Minnesota open tournament, achieving for
itself a rating of Master, but was defeated in the subsequent
invitational tournament for the state championship.  This improvement
is not as good as it looks, because the Northwestern program
runs on an extremely fast computer and looks at hundreds of thousands
of positions in deciding each move.  Champion level play without
excessive computation will require new ideas.


%3Goals and subgoals%1

	We often want a computer to find a sequence of actions that
will achieve a goal on the basis of information about the effects
of the actions and the preconditions for successful performance
of actions.  A simple example is to make a tower of blocks where a
precondition for moving one block on top of another is that both
the block to be moved and the place where it goes should be clear,
which may involve moving other blocks first.
Much recent AI research has
concerned how to express and use information about actions, their
effects and preconditions.


%3Reasoning and the representation of information%1

	Many of the difficulties in making machines perform tasks turn
out to be difficulties in deciding what information the program
should have, what further conclusions can be drawn from initial
information and how the information should be stored in the computer.
These difficulties have led to research on the subject of what is
knowledge asking many of the same questions that philosophers have
studied under the name of %2epistemology%1 - the theory of knowledge.
Mathematical logic has provided powerful means of representing
facts in computers and powerful modes of reasoning.  However, it has
turned out that not all modes of reasoning performed by humans
and needed for problem solving are represented in present systems
of mathematical logic.  Logic is excellent for the safe methods
of reasoning that never lead to error from true premises, but
intelligence also requires methods of reasoning that only generate
conjectures.

	McCarthy at Stanford University has studied how to represent
facts about sources of knowledge, such as the fact that travel
agents know airline schedules which would be required by a program
for planning trips.  It has proved especially difficult to represent
facts about concurrent actions - one action starts while others
contine.


%3Observing and acting in the physical world%1

	Besides purely symbolic problems like chess and mathematics,
an intelligent machine must be able to see and hear and it must be
able to control motion and to make things.  Programs have been written
that find objects by tracing outlines of color or brightness changes
or by growing regions of a single color or texture.
Programs that recognize and produce human speech have been written.
Some of them recognize hundreds of isolated words, and some of them
can handle connected speech if it is not too difficult.
There are also programs that drive a vehicle avoiding obstacles and
programs that assemble objects like automobile water pumps out of
parts.

	Industrial robots that do strenuous or dangerous tasks have
been in use for many years.  Almost all of them are programmed to
repeat the same exact sequence of actions such as putting an object
found in a fixed location
in a punch press or a furnace and removing it later.  The only variability
in their programs is that they can stop if an external device detects
something wrong.  Nevertheless, using such a robot is more flexible than
building a special machine for each such job that has to be scrapped
when the production task changes.  Industrial robots can be reprogrammed
for new tasks.

	Industrial robots that use television cameras to find objects
and guide their manipulation have come recently into use at Hitachi
in Japan and at General Motors.  Thomas Binford at Stanford University
has developed a language called AL for writing the programs that control
industrial robots.


%3Pattern matching%1

	All these tasks require computers to store patterns and to
recognize objects in scenes by matching the pattern.  For example,
a computer can store its idea of a dog as a collection of legs, tail
etc., each of a given shape and connected in the right way.  Then
it can try to find dogs in a picture by matching the dog pattern
with parts of the picture.  The program
must compute how a dog will look with its legs in some position
looked at from some angle and partly hidden by other objects.  Actually,
in order to recognize dogs it must do this backwards, deciding what
kind of dog would lead to the appearance it sees.

	General principles of pattern description and techniques
for pattern matching apply to recognizing dogs and recognizing
chess positions that permit attacks on the opponent's king.

	Minsky and his students at Massachusetts Institute of Technology
have studied patterns of actions that they call frames.  A typical
frame is the event of visiting a restaurant which contains subframes
of being seated, ordering, waiting, eating, paying the bill and leaving.
Schank at Yale has used such frames in programs that answer questions
about stories and can fill in information omitted from the story, because
it is implicit in the frame.


%3Understanding English%1

	One idea for making an intelligent machine is to first make it
capable of understanding English and then letting it read textbooks,
encyclopedias and scientific articles.  At present, there are computer
programs that can read stories from first grade readers and answer some
questions about them.  Other programs can converse with physicians about
bacterial diseases of the blood, but all present programs are quite
limited in the subject matter they can understand.  The difficulty
is not one of vocabulary, because it is easy to read a whole dictionary
into a computer.  The problem is that understanding requires some
initial knowledge, and we haven't been able to give computers that
initial knowledge in a sufficiently general way.

	In the 1950s programs were written to translate from one
language to another.  They weren't very good, and it was some years
before it was understood that successful translation requires
that the program understand the material being translated.  The
effort that used to go into automatic translation is now going into
making computers understand better and better larger and larger
fragments of natural language.  This "understanding" is tested by
the performance of %2question answering programs%1 that answer questions
about a text on the basis of information in the text and the common
sense knowledge posessed by the program.

	Terry Winograd's program SHRDLU combined English dialog and
problem solving to answer questions and perform requested actions
in a simulated "blocks world".  SHRDLU could be requested,
"Pick up the red pyramid and put it on the green block".  SHRDLU would
figure out that "it" referred to the red pyramid, and it would
clear off the green block if necessary, and would ask "Which green
block" if there was more than one.


%3Learning from experience%1

	Humans and animals learn from their experience how to do
better next time, and machines should do the same.  An early example
was a program by Arthur Samuel for playing checkers.  The behavior
of the program was determined by a some numbers that determined how
it evaluated positions, for example the relative values of a king
and a single man.  The program would read books of games played by
master players and adjust the numbers until they predicted as many
as possible of the moves regarded as good by the masters.  Combined
with lookahead this made an excellent program.  A version of
Samuel's program, without the learning, has recently been marketed
for playing through a TV set.

	The ability of a program to learn from experience depends on
how its behavior is represented within the machine.  If it is to
learn efficiently, then what we regard as simple changes in behavior
must be represented by small changes in the way the behavior is
represeented.  With present computer programs, this isn't usually true;
in order to change a program's behavior, one must understand the program
thoroughly and make changes in a number of places.

	This must be contrasted with teaching a human.  If you want
to teach someone to play tic-tac-toe or solve an algebra problem,
you can tell him the rules and rely on his intelligence to apply
them.  With computers it as though all education were by brain surgery.

	One of the research goals of artificial intelligence is to
to change this by developing programs with %2common sense%1 that can
take instructions and combine it with their own knowledge.

	Samuel's program is an example of learning to do something.
Learning to recognize objects has been easier.  Early pattern recognition
programs learned to classify objects such as images of letter of the
alphabet into categories, and more recent programs, such as one written
by Patrick Winston learn to classify objects according the the presence
of subobjects related in a specified way.  Winston's example is recognizing
an arch as consisting of three objects one of which is supported by
the other two which are not touching each other.  An arcade is learned
as a line of arches arranged so that there is a path under all of them.


%3Expert programs%1

	Feigenbaum and Lederberg at Stanford pioneered the development
of programs that embody the knowledge of an expert in some field.  Such
programs are developed by interviewing experts and getting them to help
improve further versions of the program.  DENDRAL is expert in determining
the structure of an organic compound from mass spectrograph observations,
and MYCIN helps a doctor diagnose bacterial infections of the blood,
recommending tests and treatment and recommending further tests and
treatment based on the results of the first.  MYCIN is intended
only to make suggestions,
and the doctor still must understand the reasons for everything he does.

	The domain of each of these expert programs is very narrow.


%3Information processing psychology%1

	The development of artificial intelligence and the study of
human intelligence are closely related, and the information processing
approach to psychology has mainly replaced behaviorism which was concerned
with finding direct relations between stimuli received by organisms and
their responses.  The information processing approach, initiated by
Allen Newell and Herbert Simon in the 1950s, writes computer
programs that match complex problem solving behavior.
Unlike stimulus-response theories, information processing theories do
not postulate direct relations between inputs and outputs, because the
internal processes can be very complex.
Both artificial intelligence and information processing psychology must
determine what intellectual mechanisms are required to solve
different kinds of problems.


%3Studying artificial intelligence%1

	Artificial intelligence is a young and difficult branch of
computer science.  Studying it requires the ability to program
a computer especially using programming languages such as LISP popular in AI
research.  Other branches of computer science such the theory of the
correctness of computer programs and complexity theory that studies
how much computing is required to solve various kinds of problems
are also important.

	There is less to learn than in physics or mathematics
in order to reach the frontier of the subject.  Indeed much of what
the student does learn is controversial and some of it is probably wrong.

	Besides connections with psychology, artificial intelligence
needs facts from and contributes to mathematical logic, linguistics
and the physiology of the nervous system.
Finally, it studies many questions that are also
studied by philosophers from a different point of view.

	All present artificial intelligence programs lack any general
view of the world and of actions and events.  Until a breakthrough in
this area occurs, human-level intelligence except in narrow domains
is far off.

%3References%1

%2Artificial Intelligence and Natural Man%1 by Margaret Boden
is critical and detailed but non-technical.

%2Artificial Intelligence%1 by Patrick Winston is the most popular
textbook as of the middle of 1978.

%2Problem Solving Methods in Artificial Intelligence%1 by Nils Nilsson
is an older textbook.

%2Human Problem Solving%1 by Allen Newell and Herbert Simon
connects artificial intelligence and psychology.
.skip to column 1
search, pattern matching, learning, representation
What man can understand about how man or machine can solve problems.
Torres y Quevedo
Turing
Chess
Generality
Heuristics and epistemology
Plenty for the ambitious lad to do.
What to read and what to learn.
	computer programming including LISP, mathematical logic, mathematics
in general, analytic philosophy, Stanford, M.I.T. and CMU., Winston, Nilsson
AI and the future of man.
comparison with science fiction

1. Introduction
	a. definition
	b. importance and difficulty
	c. computers
	d. chess 4.6 and the famous match

2. History and present state

3. Problems and methods
	a. epistemology and heuristics
	b. patterns and pattern matching
	c. heuristic search
	d. problem solving, e.g. finding a sequence of actions
	e. the problem of generality
	f. AI languages
	g. natural language
	h. learning
	i. representation
	j. physiology

4. AI and the future
	a. AI in science fiction
	b. the prospects
	c. the problem for humanity

5. Literature

Pictures and diagrams
	a. a scene and representations of information about it